package 数组.二分查找;

public class Main {
    public int search(int[] nums, int target) {
        //采用左闭右闭的二分查找模板
        int l = 0, r = nums.length - 1;
        int mid = 0;
        while (l <= r) {
            mid = (r - l) / 2 + l;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return -1;
    }

    //求x的算数平方根
    public int mySqrt(int x) {
        int l = 0, r = x;
        int ans = -1;
        while (l <= r) {
            int mid = (r - l) / 2 + l;
            if (mid * mid <= x) {
                //寻找最右边界
                ans = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return ans;
    }

    public int removeElement(int[] nums, int val) {
        //使用两个指针 i和j指针,如果不等把j的元素复制到i上面去，如果相等，j++，i不发生变化即可
        int i = 0;
        for (int j = 0; j < nums.length; j++) {
            if (nums[j] != val) {
                nums[i] = nums[j];
                i++;
            }
        }
        return i;
    }

    //主要是对于复数平方之后和正数之间的一个比较关系
    public int[] sortedSquares(int[] nums) {
        int arr[] = new int[nums.length];
        int i = 0;
        int j = nums.length - 1;
        int index=nums.length-1;
        while (i<=j){
             if(nums[i]*nums[i]>nums[j]*nums[j]){
                 arr[index--]=nums[i]*nums[i];
                 i++;
             }else{
                 arr[index--]=nums[j]*nums[j];
                 j--;
             }
        }
        return arr;
    }
}
